The present invention relates to the field of database systems. More specifically, in one embodiment the invention provides a system and method for evaluating database queries.
Many applications of database systems have evolved over the past several years, and the size of the databases managed by these applications has become staggering in some instances. As the size of a managed database becomes large, it becomes increasingly difficult to evaluate the database to identify entries meeting particular query conditions. As an example, reservation systems often include millions of entries, and from these entries a single entry must be quickly located in order to serve a consumer. In other applications, such as manufacturing operations, millions of entries must be evaluated to identify which products, for example, meet certain manufacturing quality control criteria.
Historically, such queries were evaluated by "looking at" each entry in the database individually, and compiling the results as the entries were evaluated. A variety of techniques have been developed for evaluating such queries in a more efficient manner, however. For example, the use of indexes has become common. In an indexed database, a commonly queried field in the database is provided with a separate index field. When a query is applied against the database, it is then no longer necessary to evaluate each entry, enabling much faster access to a desired entry in a database. Such systems now commonly use a "b-tree" structure, as described in, for example, Knuth et al., The Art of Computer Programming, (1973). See Volume 3, Sorting and Searching, incorporated herein by reference for all purposes.
While meeting with some success, prior techniques have also met with certain limitations. For example, in indexed searching systems the size of the index can often become unwieldy both in terms of the size of the index and the time it takes to utilize the index. Moreover, when complex queries are imposed on the system, it often becomes difficult or impossible to use indexed systems because the parameters used in a complex query often have no index. Further, databases in which the data within the database are "denormalized" present particular difficulty, and procedures may need to be utilized to put the data in an acceptable form.
In the case of large databases, such complex queries can effectively not be performed, even on large computer systems. Moreover, the storage requirements of an index for such complex queries that span all fields would be unreasonably large.
From the above it is seen that an improved system and method for performing complex queries in a database system is needed.